DNA methylation analysis has been applied to determine the primary site of cancer; however, robust and accurate prediction of cancer types with a minimum number of sites is still a significant scientific challenge. To build an accurate and robust cancer type prediction tool with a minimum number of DNA methylation sites, we internally benchmarked different DNA methylation site selection and ranking procedures, as well as different classification models. We used The Cancer Genome Atlas dataset (26 cancer types with 8296 samples) to train and test models and used an independent dataset (17 cancer types with 2738 samples) for model validation. A deep neural network model using a combined feature selection procedure (named MethyDeep) can predict 26 cancer types using 30 methylation sites with superior performance compared with the known methods for both primary and metastatic cancers in independent validation datasets. In conclusion, MethyDeep is an accurate and robust cancer type predictor with the minimum number of DNA methylation sites; it could help the cost-effective clarification of cancer of unknown primary patients and the liquid biopsy-based early screening of cancers.